package solutionsdemo;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 黎鹤舞
 * Date: 2024-01-29
 * Time: 23:03
 */

/**
 * 通过中序遍历和后序遍历 实现二叉树创建
 */
public class BuildTree2 {
    //
    public int postIndex = 1;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTreeChild(inorder,postorder, 0,postorder.length-1);
    }

    public TreeNode buildTreeChild(int[] inorder, int[] postorder,int inBegan, int inEnd) {
        if(inBegan > inEnd) {
            return null;
        }
        //新建一个根节点
        TreeNode root = new TreeNode(postorder[postorder.length - postIndex]);
        postIndex++;
        int rootIndex = getKeyIndex(inorder,inBegan,inEnd, root.val);
        root.right = buildTreeChild(inorder,postorder,rootIndex+1, inEnd);
        root.left = buildTreeChild(inorder,postorder,inBegan,rootIndex-1);
        return root;
    }

    private int getKeyIndex(int[] inorder, int inBegan, int inEnd, int val) {
        for(int i = inBegan; i <= inEnd; i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return  -1;
    }
    private int getKeyIndex2(int[] inorder, int inBegan, int inEnd, int val) {
        for(int i = inBegan; i <= inEnd; i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return  -1;
    }
}
